package com.lw.leetcode.arr.c;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**149. 直线上最多的点数
 * @Author liw
 * @Date 2021/6/24 9:35
 * @Version 1.0
 */
public class MaxPoints {

    public static void main(String[] args) {
        MaxPoints test = new MaxPoints();

//        int[][] arr = {{1, 0}, {0, 0}, {3,0}, {4,0}};
//        int[][] arr = {{0, 1}, {0, 2}, {0,3}};

        //  {{1,1},{2,2},{3,3}} 3
//        int[][] arr = {{1, 1}, {2, 2}, {3, 3}};

        // [[0,0],[1,-1],[1,1]] 2
//        int[][] arr = {{1, 1}, {0, 0}, {1,-1}};

        // {{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}} 4
//        int[][] arr= {{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}};

        // [[0,1],[0,0],[0,4],[0,-2],[0,-1],[0,3],[0,-4]] 7
        int[][] arr = {{0,1},{0,0},{0,4},{0,-2},{0,-1},{0,3},{0,-4}};

        int i = test.maxPoints(arr);
        System.out.println(i);
    }


    public int maxPoints(int[][] points) {
        int length = points.length;
        if (length < 3) {
            return length;
        }
        Map<String, Integer> map = new HashMap<>(length * length);

        int max = 1;
        String key;
        for (int i = 0; i < length - 1; i++) {
            for (int j = i + 1; j < length; j++) {
                int[] a = points[i];
                int[] b = points[j];
                int x = a[0] - b[0];
                int y = a[1] - b[1];
                if (y== 0) {
                    key = String.valueOf(a[1]);
                } else {
                    int min = min(x, y);
                    x /= min;
                    y /= min;
                    int x1 = a[0] * y - a[1] * x;
                    int y1 = y;
                    min = min(x1, y1);
                    x1 /= min;
                    y1 /= min;
                    int[] arr = new int[]{x, y, x1, y1};
                    key = Arrays.toString(arr);
                }
                Integer value = map.get(key);
                if (value == null) {
                    map.put(key, 1);
                } else {
                    map.put(key, value + 1);
                    max = Math.max(value + 1, max);
                }

            }
        }
        return (int) Math.pow(max << 1, 0.5) + 1;
    }

    public static int min(int x, int y) {
        if (x == 0) {
            return y;
        }
        int a = x < 0 ? ~x + 1 : x;
        int b = y < 0 ? ~y + 1 : y;
        if (a < b) {
            int t = a;
            a = b;
            b = t;
        }
        while (b != 0) {
            if (a == b) {
                break;
            } else {
                int k = a % b;
                a = b;
                b = k;
            }
        }
        return x < 0 ? ~a + 1 : a;
    }

}
